/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        652.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/15 17:09
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
//
//两棵树重复是指它们具有相同的结构以及相同的结点值。
#include "../header.h"
#include <iostream>
#include <sstream>

//class Solution {
//public:
//    vector<TreeNode *> findDuplicateSubtrees(TreeNode *root) {
//        traverse(root);
//        return list;
//    }
//
//private:
//    unordered_map<string, int> subtrees;
//    vector<TreeNode *> list;
//
//    string traverse(TreeNode *root) {
//        if (root == nullptr)
//            return "#";
//        string left = traverse(root->left);
//        string right = traverse(root->right);
////        ostringstream oss;
////        oss << left << "," << right<< "," << root->val;
////        string subtree = oss.str();
//        string subtree = left + "," + right + "," + to_string(root->val);
//        if (subtrees[subtree] == 1)
//            list.emplace_back(root);
//        subtrees[subtree]++;
//        return subtree;
//    }
//};
class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {

        unordered_map<long long, int> ids;
        unordered_map<int, int> counts;
        vector<TreeNode*> res;
        dfs(root, ids, counts, res);
        return res;
    }

private:
    int dfs(TreeNode* root, unordered_map<long long, int>& ids,
            unordered_map<int, int>& counts, vector<TreeNode*>& res)
    {
        if (root == nullptr) return 0;

        long long key = (static_cast<unsigned long long>(root->val) << 32) |
                        (dfs(root->left, ids, counts, res) << 16) |
                        (dfs(root->right, ids, counts, res));

        int id;
        auto it = ids.find(key);
        if (it != ids.end()) {
            id = it->second;
        }
        else {
            id = ids[key] = ids.size() + 1;
        }
        if (++counts[id] == 2) res.push_back(root);
        return id;
    }
};